class shudu {
    // 9 个 9*9 的索引
    static jiu = {
        0: [[0,0],[0,1],[0,2],[1,0],[1,1],[1,2],[2,0],[2,1],[2,2]],
        1: [[0,0],[0,1],[0,2],[1,0],[1,1],[1,2],[2,0],[2,1],[2,2]].map(_ => [_[0] + 3,_[1]]),
        2: [[0,0],[0,1],[0,2],[1,0],[1,1],[1,2],[2,0],[2,1],[2,2]].map(_ => [_[0] + 6,_[1]]),
        3: [[0,0],[0,1],[0,2],[1,0],[1,1],[1,2],[2,0],[2,1],[2,2]].map(_ => [_[0],_[1] + 3]),
        4: [[0,0],[0,1],[0,2],[1,0],[1,1],[1,2],[2,0],[2,1],[2,2]].map(_ => [_[0] + 3,_[1] + 3]),
        5: [[0,0],[0,1],[0,2],[1,0],[1,1],[1,2],[2,0],[2,1],[2,2]].map(_ => [_[0] + 6,_[1] + 3]),
        6: [[0,0],[0,1],[0,2],[1,0],[1,1],[1,2],[2,0],[2,1],[2,2]].map(_ => [_[0],_[1] + 6]),
        7: [[0,0],[0,1],[0,2],[1,0],[1,1],[1,2],[2,0],[2,1],[2,2]].map(_ => [_[0] + 3,_[1] + 6]),
        8: [[0,0],[0,1],[0,2],[1,0],[1,1],[1,2],[2,0],[2,1],[2,2]].map(_ => [_[0] + 6,_[1] + 6]),
    };
    // fn(n,x,y)
    static print(arr,fn) {
        let tmp = "";
        fn = fn || (x => x + "\t");
        for (let i = 0;i < 9;i++) {
            tmp = "";
            for (let j = 0;j < 9;j++) {
                tmp += fn(arr[i][j],j,i);
            }
            console.log(tmp);
        }
    }
    constructor(board) {
        // 记录 9 * 9 个格子里装了什么
        this.content = [];
        // 记录 没填空的格子能填什么 9*9*n
        this.ok = {
            // "03": {
            //     lind: 0,
            //     nind: 3,
            //     arr: []
            // }
        };
        this._ok = [];
        this.init(board);
        this.log = [];
        this.result = [];
    }
    init(board) {
        board.forEach((line,lind) => {
            this.content.push([]);
            line.forEach((num,nind) => {
                if (num === '.') {
                    this.content[lind].push(0);
                    this.ok[`${lind}${nind}`] = {
                        jiu: parseInt(lind / 3) * 3 + parseInt(nind / 3),
                        lind: lind,
                        nind: nind,
                        arr: [],
                        selectInd: 0
                    };
                } else {
                    this.content[lind].push(+num);
                }
            });
        });
        let t = '';
        for (let okInd in this.ok) {
            let ok = this.ok[okInd];
            let has = [];
            shudu.jiu[ok.jiu].forEach(xy => {
                t = board[xy[1]][xy[0]];
                if (t !== '.') {
                    has.push(t);
                }
            });
            for (let i = 0;i < 9;i++) {
                t = this.content[i][ok.nind];
                if (t !== 0 && !has.includes(t)) {
                    has.push(t);
                }
                t = this.content[ok.lind][i];
                if (t !== 0 && !has.includes(t)) {
                    has.push(t);
                }
            }
            has = has.map(_ => +_);
            for (let i = 1;i <= 9;i++) {
                if (!has.includes(i)) {
                    this.ok[okInd].arr.push(i);
                }
            }
        }
        for (let okInd in this.ok) {
            let ok = this.ok[okInd];
            if (ok.arr.length === 1) {
                this.content[ok.lind][ok.nind] = ok.arr[0];
                delete this.ok[okInd];
            } else {
                this._ok.push(ok);
            }
        }
        // shudu.print(this.content,(n,x,y) => {
        //     if (`${y}${x}` in this.ok) {
        //         return this.ok[`${y}${x}`].arr.join('') + '\t';
        //     } else {
        //         return `${n}\t`;
        //     }
        // });
    }

    check(y,x,jiu,n) {
        let ok = true;
        let _jiu = shudu.jiu[jiu];
        for (let i = 0;ok && i < 9;i++) {
            if (this.content[y][i] === n || this.content[i][x] === n || this.content[_jiu[i][1]][_jiu[i][0]] === n) {
                if (this.content[y][i] === n) {
                    this.log.push({
                        type: 'error',
                        x: i,
                        y: y,
                        n: n,
                        ok: false
                    });
                } else if (this.content[i][x] === n) {
                    this.log.push({
                        type: 'error',
                        x: x,
                        y: i,
                        n: n,
                        ok: false
                    });
                } else {
                    this.log.push({
                        type: 'error',
                        x: _jiu[i][0],
                        y: _jiu[i][1],
                        n: n,
                        ok: false
                    });
                }
                ok = false;
            }
        }
        return ok;
    }
    // 回溯算法
    getResult() {
        this.log = [];
        let test = (okInd) => {
            if (okInd >= this._ok.length) {
                this.result = JSON.parse(JSON.stringify(this.content));
                return true;
            } else {
                let ok = this._ok[okInd];
                // console.log(`okInd = ${okInd}\tx = ${ok.nind}\ty = ${ok.lind}`);
                this.content[ok.lind][ok.nind] = 0;
                for (let i = 0;i < ok.arr.length;i++) {
                    this.log.push({
                        type: 'before',
                        x: ok.nind,
                        y: ok.lind,
                        n: ok.arr[i],
                        // ok: true
                    });
                    if (this.check(ok.lind,ok.nind,ok.jiu,ok.arr[i])) {
                        this.log.push({
                            type: 'check',
                            x: ok.nind,
                            y: ok.lind,
                            n: ok.arr[i],
                            ok: true
                        });
                        this.content[ok.lind][ok.nind] = ok.arr[i];
                        if (test(okInd + 1)) {
                            this.content[ok.lind][ok.nind] = 0;
                            return true;
                        }
                    } else {
                        this.content[ok.lind][ok.nind] = 0;
                        this.log.push({
                            type: 'check',
                            x: ok.nind,
                            y: ok.lind,
                            n: ok.arr[i],
                            ok: false
                        });
                    }
                }
                this.content[ok.lind][ok.nind] = 0;
                return false;
            }
        };
        if (this._ok.length) {
            test(0);
        } else {
            return
        }
    }
}

/**
 * @param {character[][]} board
 * @return {void} Do not return anything, modify board in-place instead.
 */
var solveSudoku = function(board) {
    let sd = new shudu(board);
    sd.getResult();
    sd.result.forEach((line,lind) => {
        line.forEach((num,nind) => {
            board[lind][nind] = `${num}`;
        });
    });
    return board;
};

module.exports = {
    solveSudoku
}
